package com.xinheyun.demo.leetcode;

import java.util.*;
import org.w3c.dom.NodeList;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/9/8 10:25
 * @version:v1.0
 */
public class test502 {

    public static void main(String[] args) {
        test502 test502 = new test502();
        System.out.println(test502.findMaximizedCapital03(10, 0, new int[]{1, 2, 3}, new int[]{0, 1, 2}));
            //1.0 1
          // 2.1 2

    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int[][] list = new int[k + 1][capital.length];
        int ans = 0;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < capital.length; j++) {
                for (int k1 = 0; k1 < capital.length; k1++) {
                    if (capital[k1] <= list[i - 1][j]) {
                        int sum = list[i - 1][j] + profits[k1];
                        if (sum > list[i][k1]) {
                            list[i][k1] = sum;
                            ans = sum;
                        }
                    }
                }
            }
        }
        return ans;
    }



        public int findMaximizedCapital_01(int k, int w, int[] profits, int[] capital) {
            int n = profits.length;
            int curr = 0;
            int[][] arr = new int[n][2];

            for (int i = 0; i < n; ++i) {
                arr[i][0] = capital[i];
                arr[i][1] = profits[i];
            }
            Arrays.sort(arr, (a, b) -> a[0] - b[0]);

            PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
            for (int i = 0; i < k; ++i) {
                while (curr < n && arr[curr][0] <= w) {
                    pq.add(arr[curr][1]);
                    curr++;
                }
                if (!pq.isEmpty()) {
                    w += pq.poll();
                } else {
                    break;
                }
            }

            return w;
        }


    public int findMaximizedCapital03(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new int[]{capital[i], profits[i]});
        }
        //根据profits排序
        Collections.sort(list, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        int i = 0;
        //k次循环
        while(k-->0) {
            //循环list的长度
            while ( i < n && list.get(i)[0] <= w) {
                q.add(list.get(i++)[1]);
            }
            if (q.isEmpty()) {
                break;
            }
            w += q.poll();
        }
        return w;
    }


}
